/**
 * 
 */
package com.gwcloud.leetcode.tags.backtrace;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
 * @ClassName   : Leetcode040 
 * @author      : ganwei 
 * @date        : 2020年5月7日
 * @Description : Leetcode040
 */
public class Leetcode0040 {
	private List<List<Integer>> result = new ArrayList<>();
	/**
	 * -解题思路，回溯算法
	 */
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if(candidates.length == 0){
            return result;
        }
        Arrays.sort(candidates);
        backtrack(candidates,target,new ArrayList<Integer>(),0);
    	return result;
    }
    
    public void backtrack(int[] candidates, int target, List<Integer> li, int index){
    	if(target == 0){
    		result.add(new ArrayList<>(li));
    		return;
    	}
    	
    	if(target < 0){
    		return;
    	}
    	
    	for(int i = index; i < candidates.length; i++){
    		if(i > index && candidates[i] == candidates[i - 1]){ 
    			continue;
    		}
    		
    		li.add(candidates[i]);
    		backtrack(candidates, target-candidates[i], li, i+1);
    		li.remove(li.size()-1);
    	}
    }
    public static void main(String[] args){
    	Leetcode0040 l040 = new Leetcode0040();
    	int[] candidates = {14,6,25,9,30,20,33,34,28,30,16,12,31,9,9,12,34,16,25,32,8,7,30,12,33,20,21,29,24,17,27,34,11,17,30,6,32,21,27,17,16,8,24,12,12,28,11,33,10,32,22,13,34,18,12};
    	l040.combinationSum2(candidates, 27);
    	for(List<Integer> l : l040.result){
    		for(Integer i : l){
    			System.out.print(i+' ');
    		}
    		System.out.println();
    	}
    }
}
